class Solution
{
public:
    // 动态规划 复杂度 O(n^2)
    long long countQuadruplets(vector<int> &nums)
    {
        int n = nums.size();
        long long result = 0;

        // tripleDp[k][num] 表示四元组(i, j ,k ,l) 的前三元 (i, j ,k) 满足 nums[i] < nums[k] < nums[j] == num 的的个数
        vector<vector<long long>> tripleDp(n, vector<long long>(n + 1, 0));
        for (int k = 2; k < n - 1; ++k)
        {
            int lowerCount = 0;
            for (int i = 0; i < k; ++i)
            {
                if (nums[i] < nums[k])
                {
                    ++lowerCount;
                }
                else
                {
                    tripleDp[k][nums[i]] = lowerCount;
                }
            }
        }

        // 求前缀和，则 tripleDp[k][num] 表示 (i, j ,k) 满足 nums[i] < nums[k] < nums[j] <= num 的的个数
        for (auto &dp : tripleDp)
        {
            partial_sum(dp.begin(), dp.end(), dp.begin());
        }

        // 枚举第四个元素
        for (int l = 3; l < n; ++l)
        {
            for (int k = 0; k < l; ++k)
            {
                if (nums[k] < nums[l]) // 实际上应该不用判断，因为tripleDp[k]的前nums[k]个元素都是0
                {
                    result += tripleDp[k][nums[l] - 1];
                }
            }
        }
        return result;
    }

    // 枚举中间两元，再二分查找边上两元，看上去是 O(n^2 * logn)
    // 但实际上既要插入又要查找，插入和随机访问至少有一个是O(n)的，最终复杂度O(n^3)会超时
    long long countQuadruplets(vector<int> &nums)
    {
        int n = nums.size();
        long long result = 0;

        // (i, j, k, l)
        set<int> leftNums{nums[0]};
        for (int j = 1; j < n - 2; ++j)
        {
            set<int> rightNums{nums[n - 1]};
            for (int k = n - 2; k > j; --k)
            {
                if (nums[k] < nums[j])
                {
                    long long leftCount = distance(upper_bound(leftNums.begin(), leftNums.end(), nums[k]), leftNums.begin());
                    long long rightCount = distance(upper_bound(rightNums.begin(), rightNums.end(), nums[j]), rightNums.begin());
                    result += leftCount * rightCount;
                }
                rightNums.insert(nums[k]);
            }
            leftNums.insert(nums[j]);
        }
        return result;
    }
};